/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 87111
 * Date: 2025-09-12
 * Time: 16:49
 */
public class Sort {
    /**
     * 直接插入排序
     * 时间复杂度：O(n^2)
     * 空间复杂度：O(1)
     * 稳定性：稳定
     */
    public void insertSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int tmp = array[i];
            int j = i-1;
            for (; j >= 0; j--) {
                if(tmp < array[j]) {
                    array[j+1] = array[j];
                }else {
                    //array[j+1] = tmp;
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }

    /**
     * 希尔排序
     * 时间复杂度：O(n^1.3   - n^1.5)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     */
    public void shellSort(int[] array) {
        int n = array.length;
        while(n > 1) {
            n = n / 2;
            shell(array,n);
        }
    }
    private void shell(int[] array, int n) {
        for (int i = n; i < array.length; i++) {
            int tmp = array[i];
            int j = i - n;
            for (; j >= 0; j -= n) {
                if(tmp < array[j]) {
                    array[j+n] = array[j];
                }else {
                    break;
                }
            }
            array[j+n] = tmp;
        }
    }

    /**
     * 选择排序
     * 时间复杂度：O(n^2)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     */
    public void selectSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int min = i;
            for (int j = i+1; j < array.length; j++) {
                if(array[j] < array[min]) {
                    min = j;
                }
            }
            swap(array,i,min);
        }
    }
    private void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    /**
     * 堆排序
     * 时间复杂度：O(n*logn)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     */
    public void heapSort(int[] array) {
        //创建一个大根堆
        //O(n)
        createLeap(array);
        //根排序
        //O(n*logn)
        int i = array.length-1;
        while(i > 0) {
            swap(array,0,i);
            siftDown(array,0,i);
            i--;
        }
    }

    private void createLeap(int[] array) {
        int parent = (array.length - 1 -1 ) /2;
        while(parent >= 0) {
            siftDown(array,parent,array.length);
            parent--;
        }
    }

    private void siftDown(int[] array, int parent, int length) {
        int child = 2 * parent + 1;
        while(child < length) {
            if(child + 1 < length && array[child] < array[child+1]) {
                child = child + 1;
            }
            if(array[child] > array[parent]) {
                swap(array,child,parent);
                parent = child;
                child = 2*parent +1;
            }else {
                break;
            }
        }
    }
}
